package graphclustering.algorithm;

import graphclustering.data.Cluster;
import graphclustering.data.DWGraph;
import graphclustering.util.ClusteringUtils;

import java.util.ArrayList;
import java.util.List;

public class IterativeAnalysisAlgorithm {
	// private static Log logger =
    // LogFactory.getLog(IterativeAnalysisAlgorithm.class);

	static private int mergeStopThreshold = 5;

	static private float mergePercentage = (float) 0.2;

	static private int maxClusterSize = 8;

	static public Cluster analysis(DWGraph graph) {
		String result = analysisIn(graph);
		return ClusteringUtils.parse(result);
	}

	static private String analysisIn(DWGraph graph) {
		// logger.debug("Start one round analysis");
		List<Cluster> mergedClusterList = oneRoundIterClustering(graph);


		DWGraph newGraph = regenerateGraph(graph, mergedClusterList);
		if (newGraph.nodeSize < mergeStopThreshold) {
			String mergedNodeID = new String();
			int index = 0;
			for (String nodeID : newGraph.nodeIDList) {
				if (index == 0) {
					mergedNodeID = mergedNodeID + nodeID;
					index++;
				} else {
					mergedNodeID = mergedNodeID + ClusteringUtils.seperator
							+ nodeID;
				}

			}
			mergedNodeID = "(" + mergedNodeID + ")";
			return mergedNodeID;
		} else {
			return analysisIn(newGraph);
		}
	}

	static private List<Cluster> oneRoundIterClustering(DWGraph graph) {
		List<Cluster> clusterList = new ArrayList<Cluster>();

		// For each node, select a cluster candidate
		for (int i = 0; i < graph.nodeSize; i++) {
			// Select a cluster candidate of best quality for a given node
			List<Cluster> tmpClusterList = selectClusterCandidateforOneNode(
					graph, i, maxClusterSize);
			float bestClusterQuality = -100000;
			Cluster selectedCluster = null;
			for (Cluster candidate : tmpClusterList) {
				float clusterQuality = ClusteringUtils
						.calcIMValueforCandCluster(candidate, graph);
				if (bestClusterQuality < clusterQuality) {
					bestClusterQuality = clusterQuality;
					selectedCluster = candidate;
					selectedCluster.imQuality = clusterQuality;
				}
			}
			if (selectedCluster != null)
				clusterList.add(selectedCluster);
		}

		// Sort the clusterList based on the im value of each cluster in the
		// list
		/*
         * for (int i = 0; i < clusterList.size(); i++) { float currentMax =
         * clusterList.get(i).imQuality; Cluster tempCluster = null; int
         * clusterIndex = i; for (int j = i + 1; j < clusterList.size(); j++) {
         * if (clusterList.get(j).imQuality > currentMax) { currentMax =
         * clusterList.get(j).imQuality; tempCluster = clusterList.get(j);
         * clusterIndex = j; } } if (i != clusterIndex && tempCluster != null) {
         * Cluster tmp = clusterList.get(i); clusterList.set(i, tempCluster);
         * clusterList.set(clusterIndex, tmp); } }
         */

		// Provide policy to select , currently, percentage is used
		int toBeMergeClusterNum = (int) (mergePercentage * graph.nodeSize);
		List<Cluster> selectedClusterList = new ArrayList<Cluster>();

		for (Cluster tmp : clusterList) {
			if (!ClusteringUtils.overlapped(selectedClusterList, tmp)) {

				selectedClusterList.add(tmp);
				List<Integer> noneSelectedNodeIndexList = BitClusteringAlgorithm
						.getNoneSelectedNodeIndexList(selectedClusterList,
								graph);
				for (int i = 0; i < noneSelectedNodeIndexList.size(); i++) {
					float weightSum = 0.0f;
					int indexI = noneSelectedNodeIndexList.get(i);
					for (int j = 0; j < noneSelectedNodeIndexList.size(); j++) {
						int indexJ = noneSelectedNodeIndexList.get(j);
						if (i != j) {
							weightSum = weightSum + graph.graph[indexI][indexJ]
									+ graph.graph[indexJ][indexI];
						}
					}
					if (weightSum == 0.0f) {
						// logger.debug("add orphan node:" +
                        // graph.nodeIDList.get(indexI));
						tmp.atomicNodeIDList.add(graph.nodeIDList.get(indexI));
					}
				}
			}
			if (selectedClusterList.size() > toBeMergeClusterNum)
				break;
		}

		return selectedClusterList;
	}

	static private DWGraph regenerateGraph(DWGraph oldGraph /* input */,
			List<Cluster> mergedClusterList/* input */) {

		List<String> newNodeIDList = new ArrayList<String>();

		List<String> allMergedNodeIDList = new ArrayList<String>();
		for (Cluster tmp : mergedClusterList) {
			String newNodeID = new String();
			int i = 0;
			for (String atomicNodeID : tmp.atomicNodeIDList) {
				if (i == 0)
					newNodeID = newNodeID + atomicNodeID;
				else
					newNodeID = newNodeID + ClusteringUtils.seperator
							+ atomicNodeID;
				i++;
			}
			newNodeID = "(" + newNodeID + ")";
			newNodeIDList.add(newNodeID);
			allMergedNodeIDList.addAll(tmp.atomicNodeIDList);
		}
		ClusteringUtils.eniminateDuplica(allMergedNodeIDList);

		DWGraph newGraph = new DWGraph();
		newGraph.nodeSize = oldGraph.nodeSize - allMergedNodeIDList.size()
				+ newNodeIDList.size();

		for (String nodeID : oldGraph.nodeIDList)
			if (!allMergedNodeIDList.contains(nodeID))
				newGraph.nodeIDList.add(nodeID);

		for (String nodeID : newNodeIDList)
			newGraph.nodeIDList.add(nodeID);

		newGraph.graph = new float[newGraph.nodeSize][newGraph.nodeSize];

		int newI = 0, newJ = 0;
		for (int i = 0; i < oldGraph.nodeSize - allMergedNodeIDList.size(); i++) {
			if (newGraph.nodeIDList.contains(oldGraph.nodeIDList.get(i))) {
				newI = newGraph.nodeIDList.indexOf(oldGraph.nodeIDList.get(i));
			} else
				continue;

			for (int j = 0; j < oldGraph.nodeSize - allMergedNodeIDList.size(); j++) {
				if (newGraph.nodeIDList.contains(oldGraph.nodeIDList.get(j))) {
					newJ = newGraph.nodeIDList.indexOf(oldGraph.nodeIDList
							.get(j));
				} else
					continue;
				newGraph.graph[newI][newJ] = oldGraph.graph[i][j];
			}
		}

		int unChangedNodeNum = oldGraph.nodeSize - allMergedNodeIDList.size();
		int newNodeNum = newNodeIDList.size();
		for (int i = 0; i < unChangedNodeNum; i++) {
			int mergedClusterIndex = 0;
			for (int j = unChangedNodeNum; j < newGraph.nodeSize; j++) {
				newGraph.graph[i][j] = ClusteringUtils.calcWeight(oldGraph,
						newGraph.nodeIDList.get(i), mergedClusterList
								.get(mergedClusterIndex));
				mergedClusterIndex++;
			}
		}

		int mergedClusterIndex = 0;
		for (int i = unChangedNodeNum; i < newGraph.nodeSize; i++) {
			for (int j = 0; j < unChangedNodeNum; j++) {
				newGraph.graph[i][j] = ClusteringUtils.calcWeight(oldGraph,
						mergedClusterList.get(mergedClusterIndex),
						newGraph.nodeIDList.get(j));
			}
			mergedClusterIndex++;
		}

		for (int j = unChangedNodeNum; j < newGraph.nodeSize; j++) {
			for (int i = unChangedNodeNum; i < newGraph.nodeSize; i++) {
				newGraph.graph[i][j] = ClusteringUtils.calcWeight(oldGraph,
						mergedClusterList.get(i - unChangedNodeNum),
						mergedClusterList.get(j - unChangedNodeNum));
			}
		}

		return newGraph;
	}

	public static List<Cluster> selectClusterCandidateforOneNode(DWGraph graph,
			int index, int maxNodeNum) {
		// Initiate the candidateClusterList
		List<Cluster> candidateClusterList = new ArrayList<Cluster>();

		// Get all possible clusters by enumerate the direct-neighbor node of
		// the index node
		List<String> firstNeighborNodeIDList = ClusteringUtils
				.getNeighborNodeIDListFor(graph.nodeIDList.get(index), graph);
		// if(graph.nodeSize==6){
		// System.out.println(firstNeighborNodeIDList);
		// System.out.println(graph.graph);
		// }
		List<Cluster> firstCircle = ClusteringUtils.getAllPossibleCombination(
				firstNeighborNodeIDList, maxNodeNum - 1);

		/*
         * //For each cluster in the first circle cluster, //Get all possible
         * clusters by enumerate the direct-neighbor node of the nodes in the
         * tmp cluster for (Cluster tmp: firstCircle) { List<String>
         * secondNeighborNodeIDList =
         * getNeighborNodeIDListFor(tmp.atomicNodeIDList,graph); List<String>
         * existingNodeIDList = new ArrayList<String>();
         * existingNodeIDList.add(graph.nodeIDList.get(index));
         * existingNodeIDList.addAll(tmp.atomicNodeIDList);
         * deleteOverlapNodeIDs(secondNeighborNodeIDList, existingNodeIDList);
         * deleteOverlapNodeIDs(secondNeighborNodeIDList,
         * firstNeighborNodeIDList); List<Cluster> secondCircle =
         * getAllPossibleCombination(secondNeighborNodeIDList, maxNodeNum-2);
         * addExistingNodeIDsFor(secondCircle, existingNodeIDList);
         * candidateClusterList.addAll(secondCircle); }
         */

		List<String> existingNodeIDList = new ArrayList<String>();
		existingNodeIDList.add(graph.nodeIDList.get(index));
		ClusteringUtils.addExistingNodeIDsFor(firstCircle, existingNodeIDList);
		candidateClusterList.addAll(firstCircle);

		// Cluster oneNodeCluster = new Cluster();
		// oneNodeCluster.atomicNodeIDList.add(graph.nodeIDList.get(index));
		// candidateClusterList.add(oneNodeCluster);

		return candidateClusterList;

	}

}
